/**
 * Created with IDEA
 * author:ju bai
 * Date:2021/7/9
 * Time:17:07
 **/
public class MergeSort {
    /**
     * 归并排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     */

    //递归
    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length - 1);
    }


    public static void mergeSortInternal(int[] array, int low, int high) {
        if (low >= high) return;
        int mid = (low + high) / 2;
        mergeSortInternal(array, low, mid);//左
        mergeSortInternal(array, mid + 1, high);//右
        //合并
        merge(array, low, mid, high);
    }

    public static void merge(int[] array, int low, int mid, int high) {
        /*int s1 = low;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = high;
        while(s1<=e1&&s2<=e2){

        }*/
        int s1 = low;
        int s2 = mid + 1;
        int[] tmp = new int[high - low + 1];
        int k = 0;//tmp数组的下标
        while (s1 <= mid && s2 <= high) {
            if (array[s1] <= array[s2]) {
                /*tmp[k] = array[s1];
                k++;
                s1++;*/
                tmp[k++] = array[s1++];
            }
            if (array[s1] >= array[s2]) {
                tmp[k++] = array[s2++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= mid) {
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i + low] = tmp[i];
        }
    }


    //非递归
    public static void mergeSort2(int[] array) {
        for (int i = 1; i < array.length; i *= 2) {
            merge2(array, i);
        }
    }
    

    public static void merge2(int[] array, int gap) {
        int s1 = 0;
        int e1 = s1 + gap - 1;
        int s2 = e1 + 1;
        int e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
        int[] tmp = new int[array.length];
        int k = 0;
        //当有两个归并段时
        while (s2 < array.length) {
            while (s1 <= e1 && s2 <= e2) {//当有两个归并段且这两个归并段都有数据
                if (array[s1] <= array[s2]) {
                    tmp[k++] = array[s1++];
                } else {
                    tmp[k++] = array[s2++];
                }
            }
            while (s1 <= e1) {
                tmp[k++] = array[s1++];
            }
            while (s2 <= e2) {
                tmp[k++] = array[s2++];
            }
            s1 = e2 + 1;
            e1 = s1 + gap - 1;
            s2 = e1 + 1;
            e2 = s2 + gap - 1 < array.length ? s2 + gap - 1 : array.length - 1;
        }
        while (s1 < array.length) {//退出上边循环后，将s1段内数据拷贝下来，因为有可能e1已经越界
            tmp[k++] = array[s1++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i] = tmp[i];
        }

    }

}
